package com.yun.algorithmproblem.leetcode;

import com.yun.datastructure.tree.binarytree.domain.TreeNode;

import java.util.LinkedList;

public class Leetcode112 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        int count = 0;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode pop = null;//最近一次弹栈的元素
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                count += curr.val;
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.left == null && peek.right == null) {
                    if(count==targetSum){
                        return true;
                    }
                }
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    count -= pop.val;
                } else {
                    curr = peek.right;
                }
            }
        }
        return false;
    }
}
